//
//  SelectSort.swift
//  CommandLineTool1
//
//  Created by May on 2025/3/26.
//

import Foundation

class Sort {
    
    static func selectionSort_1<T: Comparable>(_ array: [T]) -> [T] {
        var sortedArr = array
        let n = array.count
        
        for i in 0..<n {
            var minIdx = i
            for j in (i + 1)..<n {
                if sortedArr[j] < sortedArr[minIdx] {
                    minIdx = j
                }
            }
            if minIdx != i {
                sortedArr.swapAt(minIdx, i)
            }
        }
        
        return sortedArr
    }
    
    static func selectionSort_2<T: Comparable>(_ array: inout [T]) {
        let n = array.count
        for i in 0..<n {
            var minIdx = i
            for j in (i+1)..<n {
                if array[j] < array[minIdx] {
                    minIdx = j
                }
            }
            
            if minIdx != i {
                array.swapAt(minIdx, i)
            }
        }
    }
    
    static func selectionSort( arr: inout [Int] ) {
        if arr.isEmpty || arr.count < 2 { return }
        // * count - 1
        for i in 0..<arr.count - 1 {
            var idx = i
            for j in (i + 1)..<arr.count {
                idx = (arr[idx] < arr[j] ? idx : j)
            }
            arr.swapAt(idx, i)
        }
    }
    
    static func bubbleSort1( arr: inout [Int] ) {
        if arr.isEmpty || arr.count < 2 { return }
        for i in 0..<arr.count - 1 {
            // * count - i
            for j in 1..<arr.count - i {
                if arr[j - 1] > arr[j] {
                    arr.swapAt(j - 1, j)
                }
            }
        }
    }
    
    static func bubbleSort2( arr: inout [Int] ) {
        if arr.isEmpty || arr.count < 2 { return }
        for i in (0..<arr.count).reversed() {
            for j in 0..<i {
                if arr[j] > arr[j + 1] {
                    arr.swapAt(j, j + 1)
                }
            }
        }
    }
    
    static func insertionSort( arr: inout [Int] ) {
        if arr.isEmpty || arr.count < 2 { return }
        for i in 1..<arr.count {
            
            var idx = i
            while ((idx - 1 >= 0) && (arr[idx - 1] > arr[idx])) {
                arr.swapAt(idx - 1, idx)
                idx -= 1
            }
            
//            for j in (1...i).reversed() {
//                if arr[j] < arr[j - 1] {
//                    arr.swapAt(j, j - 1)
//                } else {
//                    break
//                }
//            }
        }
    }
}
